package recursion;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Backtrack {
    /*
     * 力扣46. 全排列
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     * 使用回溯法backtrack
     *
     * @param nums 传入数组
     * @return
     * */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> list = new ArrayList<>();
        for(int i : nums){
            list.add(i);
        }
        backtrack(res,list,0,list.size());
        return res;

    }
    /*
     * 此处递归回溯
     *
     * @param res 最终结果列表
     * @param list 临时出粗当前排列数组
     * @param index 控制当前交换的位置
     * @param n 临时储存列表的长度
     * */
    private void backtrack(List<List<Integer>> res,List<Integer> list,int index,int n){
        if(index == n){
            res.add(new ArrayList<>(list));
        }

        for(int i = index;i < n;i ++){
            //交换第i个和第index个，第一遍时自己交换自己相当于没有交换
            Collections.swap(list,i,index);
            //进行回溯（递归）
            backtrack(res,list,index + 1,n);
            //撤销操作，也就是还原，防止队之后造成影响
            Collections.swap(list,i,index);
        }
    }



    /*
    * 力扣 1601. 最多可达成的换楼请求数目
    *
    * 我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。
    * 给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。
    * 一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足
    * 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。
    * 比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，
    * 应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。
    * 请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。
    *
    * 简单的理解，题目就是，右n栋楼，房间都是住满的，只有有人搬出来才能住进去，再最优的条件下，可以满足几个人的请求
    *
    * 回溯枚举全部可能
    * */

    //用来记录那个楼人数，0为住满
    int[] room;
    //res记录结果，cnt用于回溯时统计，zero和n配合，计算是否满足结果，再房间正好的时候zero和n相等
    int res = 0,cnt = 0,zero,n;
    public int maximumRequests(int n, int[][] requests) {
        room = new int[n];
        zero = n;
        this.n = n;
        dfs(requests,0);
        return res;
    }

    public void dfs(int[][] requests,int index) {
        if(index == requests.length) {
            if(zero == n) {
                res = Math.max(res,cnt);
            }

            return;
        }
        //不接受当前请求，直接进行下一个请求
        dfs(requests,index + 1);

        //接收当前请求，z用来记录zero的值，最后还给zero防止回溯对其他结果产生影响
        int z = zero;
        //同意请求后，统计当前
        cnt ++;
        int[] tmp = requests[index];
        int out = tmp[0],in = tmp[1];
        //这一系列的加减，最终都是判断当前的楼是否为零，如果为零的情况下zero最总数据是没有发生改变的
        zero -= room[out] == 0 ? 1 : 0;
        room[out] --;
        zero += room[out] == 0 ? 1 : 0;
        zero -= room[in] == 0 ? 1 : 0;
        room[in] ++;
        zero += room[in] == 0 ? 1 : 0;
        //这一边接收进行下一步递归
        dfs(requests,index + 1);
        //进行数据还原防止对其他情况造成影响
        room[in] --;
        room[out] ++;
        cnt --;
        zero = z;
    }
}
